from typing import List


class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        dp = [[nums[k]] for k in range(n)]  # 在i处结尾的最长数组

        result = []
        for i in range(n):
            for j in range(i - 1, -1, -1):
                if nums[i] % nums[j] == 0:
                    if len(dp[i]) < len(dp[j]) + 1:
                        dp[i] = dp[j] + [nums[i]]
            if len(result) < len(dp[i]):
                result = dp[i]
        return result


if __name__ == '__main__':
    s = Solution()
    r = s.largestDivisibleSubset([5, 9, 18, 54, 108, 540, 90, 180, 360, 720])
    print(r)
